import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-08-06
 * Time: 22:40
 */
public class LRUCache {
    // 自定义一个双向链表
    class DLinkedNode{
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode(){

        }

        public DLinkedNode(int _key,int _value){
            key = _key;
            value = _value;
        }
    }

    private Map<Integer,DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head,tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        // 哈希表中有没有
        DLinkedNode node = cache.get(key);
        if(node==null){
            return -1;
        }
        // 移动到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if(node==null){
            // 不存在就创建一个新节点
            DLinkedNode newNode = new DLinkedNode(key,value);
            cache.put(key,newNode);
            // 放到链表头部
            addToHead(newNode);
            size++;
            // 大小大于默认容量了
            if(size>capacity){
                // 进行删除最后的元素
                DLinkedNode tail = removeTail();
                // 删除
                cache.remove(tail.key);
                size--;
            }
        }else{
            node.value = value;
            moveToHead(node);
        }
    }

    // 将节点放到头部
    private void addToHead(DLinkedNode node){
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    // 放到头节点
    private void moveToHead(DLinkedNode node){
        // 删除节点
        removeNode(node);
        // 创建一个新的放到头节点
        addToHead(node);
    }

    // 删除节点
    private void removeNode(DLinkedNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 移动到最后
    private DLinkedNode removeTail(){
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}
